Árvores

Tópicos

Definições

Um grafo é acíclico se não contém circuito.
Árvore é um grafo acíclico e conexo.

Teoremas

Quaisquer dois vértices de uma árvore estão ligados por um único caminho.
Se G é uma árvore então |E(G)| = |V (G)|−1.

Corolário

Seja G uma árvore, x e y dois vértices de G tais que e = (x, y) ∉ E(G). Então G + e contém um único circuito.
Toda árvore com pelo menos dois vértices tem pelo menos dois vértices de grau um.

Aresta de Corte

Uma aresta de corte e é de corte se, e somente se, não existe caminho em G - e ligando os extremos de e.
Em outras palavras uma aresta e = w é de corte se:
- e é o único caminho ligando u a v
- não existe circuito contendo e

Teorema

Um grafo conexo é uma árvore se, e somente se, toda aresta é de corte

Árvore geradora

Uma árvore geradora de um grafo G é um subgrafo gerado de G que é uma árvore.
OBS:
- Todo grafo conexo contém uma árvore geradora

Árvore geradora de custo mínimo

Se G é um grafo com peso nas aresta então:

w(e) indica o peso da arestas e.
w(G) indica o peso total do grafo G.

Teoremas

A floresta de k árvores na qual tem um total de n vértices tem n - k arestas.
- k = 4 e n = 18
- m = n - k = 18 - 4 = 14 arestas
(Formula de Cayley): Seja n ∈ IN. Considere Kn o grafo completo com n vértices. Então o número de árvores geradoras de Kn é dado por τ(G) = n^n−2.
Seja G um grafo conexo então o número de árvores geradoras é τ (G) =τ(G−e) +τ (G \ e)
Kirchhoff?

Algoritmo de Krustal

Observações

Os custos são números inteiros arbitrários (positivos e negativos).
O problema tem solução se e somente se o grafo é conexo.

Ideia básica:

Seleciona a aresta de menos peso que conecta duas árvores de uma floresta.
Repita o processo até que todos os vértices estejam conectados sempre preservando a invariante de se ter uma árvore.

Exemplo do Algoritmo de Krustal

Algoritmo de Prim

Ideia básica:

Tomando como vértice inicial A, crie uma fila de prioridades classificada pelos pesos das arestas conectando A.
Repita o processo até que todos os vértices tenham sido visitados.

Exemplo do Algoritmo de Prim